//https://www.dotcpp.com/oj/contest6309_problem5.html?sid=16188736&lang=3#editor
package 题目集.动态规划.最长公共子串;

import java.util.Arrays;
import java.util.Scanner;

public class 可修改的最长公共子序列 {
    /**
     * 1.t[i]=t[j]->dp[i][j]=dp[i-1][j-1]
     * 2.t[i]!=t[j]->dp[i][j]=min(  舍弃, 修改  )
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t1 = sc.nextLine().toCharArray();
        t2 = sc.nextLine().toCharArray();
        dp=new int[t1.length][t2.length];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
        System.out.println(dfs(t1.length-1, t2.length-1));
    }

    static char[] t1;
    static char[] t2;
    static int[][] dp;
    public static int dfs(int i,int j){
        if (i<j){   //t1的长度小于t2的长度
            return Integer.MAX_VALUE;
        }
        if (j<0){   //全部舍弃
            return 0;
        }
        if (dp[i][j]!=-1){
            return dp[i][j];
        }
        int res=Integer.MAX_VALUE;
        if (t1[i]==t2[j]){
            res=dfs(i-1,j-1);
        }else {
            int no = dfs(i - 1, j);
            int update=dfs(i-1,j-1)+1; //修改,修改操作一定不会为MAX_VALUE
            res=Math.min(no,update);
        }
        dp[i][j]=res;
        return res;
    }

    public static int dpFun(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i <= n; i++) {
            dp[i][0] =1;
        }
        dp[0][0] = t1[0] == t2[0] ? 0 : 1;

        for (int i = 1; i <n; i++) {
            for (int j = 1; j <m; j++) {
                if (t1[i - 1] == t2[j - 1]) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1] + 1);
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[n][m];
    }
}
